1. Field of the Invention
This invention relates generally to circuit layout optimization and more specifically to differentiating priorities in layout optimization such that priority relativity and numerical precision are maintained at the same time.
2. Description of the Related Art
Automatic layout optimization is a powerful technique to modify a layout for design rule correctness purposes, to optimize a layout for certain objectives such as manufacturability improvement and performance tuning, and to migrate a layout from one technology to another technology.
Usually an LP (linear programming) problem is constructed in a layout optimization tool where variables represent edge locations and/or transform (cell reference) locations. FIG. 1 illustrates a spacing constraint between two edges, x1 and x2. In a hierarchical layout, the actual location of shape edge x1 ist11±t12± . . . ±t1m±x1Either “+” or “−” is used depending on the cell orientation.
Similarly, the actual location of shape edge x2 ist21±t22± . . . ±t2n±x2
The spacing constraint between the two edges shown isd_max≧(t21±t22± . . . ±t2n±x2)−(t11±t12± . . . ±t1m±x1)≧d_min
The objective is to fix violations including DRC (design rule checking) violations and DFM (design for manufacturability) violations, specified by a set of DRC rules and a set of recommended rules respectively.
Embodiments herein fix violations and minimize the perturbation of the existing layout at the same time. The minimum layout perturbation-based legalization technique is described in U.S. Pat. No. 6,189,132 “Design rule correction system and method”, the complete disclosure of which is hereby incorporated by reference. Layout perturbation includes:                1. location perturbation (locPert): min|x−xold|        2. space perturbation (spacePert): min|(x2−x1)−(x2old −x1old)|        
In the minimum layout perturbation-based legalization technique, the objective is to minimize the total cost:min(C(layout perturbations)+C(DFM violations)+C(DRC violations))where C(x) means the cost function. The objective function is a linear function. The absolute function for the layout perturbation cost can be linearized using the technique described in U.S. Pat. No. 6,189,132. The cost of moving an edge is set to be the length of the edge. The initial cost of layout perturbation is zero, since there is no perturbation initially. The cost of a DRC or DFM violation needs to be determined such that it can overcome the cost of the edge movement involved in order to fix the DRC/DFM violation. Therefore in the worst case, if all the edges in a layout need to be moved in order to fix a violation, the cost of the violation will have to be larger than the sum of all the location perturbation costs. However, typically in practice, the cost of a violation does not need to be as large as the sum of all location perturbation costs.